package com.ryujung.dp.leetCode_32;

/*
 * @lc app=leetcode.cn id=32 lang=java
 *
 * [32] 最长有效括号
 */

// @lc code=start
class Solution {

    /**
     * 使用动态规划来计算指定返回的子串是否为合法的括号序列
     * 定义 dp 表示以下标 i 字符结尾的最长有效括号的长度
     * 思路：
     * 以左括号结尾的子串一定不是最长有效括号
     * 只判断右括号结尾的子串即可
     * 状态转移函数：i结尾的是左括号时，dp[i] = [i-1]
     */
    public static int longestValidParentheses(String s) {
        int l = s.length();
        char[] sc = s.toCharArray();
        int[] dp = new int[l];
        for (int i = 0; i < l; i++) {
            
        }
        return 0;
    }

    /**
     * 参考discussion中的思路
     */
    public static int longestValidParentheses2(String s) {
        int l = s.length();
        char[] sc = s.toCharArray();
        // dp表示从i到j是否为合法的括号字串
        char leftBracket = '(';
        char rightBracket = ')';

        int sumAsc = 0, sumDesc = 0;
        int max = 0, curLength = 0, validLength = 0;
        for (int i = 0; i < l; i++) {
            sumAsc += sc[i] == leftBracket ? 1 : -1;
            curLength++;
            if (sumAsc == 0) {
                validLength = curLength;
            } else if (sumAsc < 0) {
                // 和前面的有效长度断开,重置所有当前遍历的参数
                curLength = 0;
                validLength = 0;
                sumAsc = 0;
            }
            max = max < validLength ? validLength : max;
        }

        curLength = 0;
        validLength = 0;
        for (int i = l - 1; i >= 0; i--) {
            sumDesc += sc[i] == rightBracket ? 1 : -1;
            curLength++;
            if (sumDesc == 0) {
                validLength = curLength;
            } else if (sumDesc < 0) {
                // 和前面的有效长度断开,重置所有当前遍历的参数
                curLength = 0;
                validLength = 0;
                sumDesc = 0;
            }
            max = max < validLength ? validLength : max;
        }

        return max;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses("()"));
    }

}
// @lc code=end
